package __sort

// SimplestSort 最最简单的交换排序
// 严格意义上说，连冒泡排序都不算
// 基本思想：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止
func SimplestSort(list []int) {
	for i := 0; i < len(list); i++ {
		for j := i + 1; j < len(list); j++ {
			if list[i] > list[j] {
				list[i], list[j] = list[j], list[i]
			}
		}
	}
}

// BubbleSort 冒泡排序
// 两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止
// 时间复杂度：O(n^2)
func BubbleSort(list []int) {
	// 排好序的数组，减少后面的判断
	didSwap := false
	for i := 0; i < len(list); i++ {
		didSwap = false
		for j := len(list) - 2; j >= i; j-- {
			if list[j] > list[j+1] {
				list[j], list[j+1] = list[j+1], list[j]
				didSwap = true
			}
		}
		if !didSwap {
			return
		}
	}
}

// SelectSort 选择排序
// 线性搜索数列，每次选择最小值，并交换
// 时间复杂度：O(n^2)
// 交换移动数据次数少，但是比较次数和冒泡一样多
// 总体比冒泡排序稍微好一点
func SelectSort(list []int) {
	for i := 0; i < len(list); i++ {
		min := i // 将i下标作为最小值
		for j := i + 1; j < len(list); j++ {
			if list[j] < list[min] {
				min = j
			}
		}
		if min != i {
			list[i], list[min] = list[min], list[i]
		}
	}
}

// InsertSort 插入排序
// 将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表
// 时间复杂度：O(n^2)
func InsertSort(list []int) {
	// 从第二个开始
	for i := 1; i < len(list); i++ {
		// 如果比上一个小
		if list[i] < list[i-1] {
			deal := list[i]
			mj := i
			for j := i - 1; j >= 0 && deal < list[j]; j-- {
				list[j+1] = list[j]
				mj = j
			}
			if mj != i {
				list[mj] = deal
			}
		}
	}
}

// ShellSort 希尔排序
// 希尔排序是直接插入排序的改进版本
// 思路：将整个序列分成若干组，每个组进行插入排序，整体达到基本有序后再用插入排序
// 分组的依据：一般是整个长度的一半，比如：14 -> 7 -> 3 -> 1
// 遍历每一组中的数据，进行插入排序
// 时间复杂度大约在这个范围：O(n^1.3)~O(n^2)，具体还无法用数学来严格证明它
func ShellSort(list []int) {
	// 数组长度
	n := len(list)
	for step := n / 2; step > 0; step /= 2 {
		// 7 -> 3 -> 1
		for i := step; i < n; i += step {
			// 对每组进行插入排序
			if list[i] < list[i-step] {
				deal := list[i]
				mj := i
				for j := i - step; j >= 0 && deal < list[j]; j -= step {
					// 要填上deal的下标位置
					list[j+step] = list[j]
					mj = j
				}
				if mj != i {
					list[mj] = deal
				}
			}
		}
	}
}

// HeapSort 堆排序
// 时间主要消耗：初始构建堆和在重建堆时的反复筛选
// 时间复杂度：O(nlogn)
// 这样实现的堆排序是普通的堆排序，性能不是最优的。
// 自底向上堆排序，仅仅将构建堆的时间复杂度从 O(nlogn) 改进到 O(n)，其他保持不变。
func HeapSort(list []int) {
	h := NewHeap(list)
	for _, v := range list {
		h.Push(v)
	}
	// 取出堆中的数据，这里是大堆，则每次取大的数
	n := len(list)
	for i := 0; i < n; i++ {
		x := h.Pop()
		// 填充到原来的数组
		list[n-i-1] = x
	}
}

// MergeSort 归并排序
// 将序列分成长度为1的子序列，两两排序，如此重复，直到合并完成
// 时间复杂度：O(n*logN),额外空间复杂度：O(n)
func MergeSort(list []int) {
	n := len(list)
	if n <= 1 {
		// [2]
		return
	}
	// 使用递归的方式
	// 浪费空间
	mid := len(list) >> 1
	// 左边
	MergeSort(list[:mid])
	// 右边
	MergeSort(list[mid:]) // 还是原来的数组
	// 合并
	// [3, 4]
	merge(list, mid)

	// 非递归
	// 还未实现
	//for i := 2; i < n; i*=2 {
	//	// i: 2, 4, 8
	//	for j := 0; j < n; j+=i {
	//		// j: 0, 2, 4, 6, 8
	//		// j: 0, 4, 8
	//		// j: 0, 8
	//		r := j+i
	//		if r > n {
	//			r = n
	//		}
	//		mid := j + (i >> 1)
	//		if mid > n {
	//			continue
	//		}
	//		merge(list[j:r], mid)
	//	}
	//}
}

func merge(list []int, mid int) {
	n := len(list) // n = 2, mid = 1
	if n <= 1 {
		return
	}
	newArray := make([]int, 0)
	// 偏移量
	l, r := 0, 0
	for l < mid && r < n-mid {
		lValue := list[l]     // list[0]
		rValue := list[mid+r] // list[1]
		if lValue < rValue {
			newArray = append(newArray, lValue)
			l++
		} else {
			newArray = append(newArray, rValue)
			r++
		}
	}
	// 将剩下的放进数组
	newArray = append(newArray, list[l:mid]...)   // [0:1] [1:1]
	newArray = append(newArray, list[r+mid:n]...) // [1:2] [2:2]
	// 将辅助数组放入原数组
	for i := 0; i < n; i++ {
		list[i] = newArray[i]
	}
}

// QuickSort 快速排序
// 快速排序是对冒泡排序的一种改进，也属于交换类的排序算法。
// 20世纪十大算法之一
// 核心思想：
// 通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，
// 以达到整个序列有序的目的。
// 时间复杂度：最好 O(N*logN),最坏 O(N^2)
// 空间复杂度：最好 O(logN), 最坏 O(N),
// 空间复杂度不能省，因每次必须记录pivot值
// 优化方案：
// 1. 将小的放左边，相等的放中间，大的放右边
// 2. pivot 值随机选择，或者三数取中，即随机取三个数，用中间那个
// 3. 当数组的个数比较小（7 or 50）时，使用插入排序，这也是工程项目中常用的
// 	  直接插入排序在对小数组使用时比快速排序好
// 原因：在相对有序的情况下，插入排序性能好
func QuickSort(list []int) {
	if len(list) <= 1 {
		return
	}
	// 切分
	loc := partition(list)
	// 切左边
	QuickSort(list[:loc])
	// 切右边
	QuickSort(list[loc:])
}

// 返回切元素的下标
// [1, 3, 5, 2]
// [6, 4, 2, 5]
func partition(list []int) int {
	if len(list) <= 1 {
		return 0
	}
	pivot := 0 // 第一个作为 pivot 值
	i := 1     // 从第二个开始
	j := len(list) - 1
	for i < j {
		if list[i] < list[pivot] {
			i++
		}
		if list[j] > list[pivot] {
			j--
		}
		if list[i] > list[pivot] && list[j] < list[pivot] {
			list[i], list[j] = list[j], list[i]
		}
	}
	// 当 i == j
	if list[i] <= list[pivot] {
		list[i], list[pivot] = list[pivot], list[i]
	}
	return i

}

// CountingSort 计数排序
// 一种稳定的线性时间排序算法,不需要比较
// 要求输入的数据必须是有确定范围的整数,比如年龄
// 思路：将输入的数据值转化为键存储在额外开辟的数组空间中
// 分配确定范围空间的数组arr
// 统计数组中数字的出现个数，保存到arr中
func CountingSort(list []int) {
	// [6, 6, 5, 7, 8]
	// 创建一个最大和最小范围内的数组
	max, min := findMaxAndMin(list)
	newArray := make([]int, max-min+1)
	for _, v := range list {
		newArray[v-min]++
	}
	// [1, 2, 1, 1]
	arri := 0
	for i, v := range newArray {
		for j := 0; j < v; j++ {
			list[arri] = i + min
			arri++
		}
	}
	// [5, 6, 6, 7, 8]
}

func findMaxAndMin(list []int) (int, int) {
	if len(list) == 0 {
		return -1, -1
	}
	max, min := list[0], list[0]
	for _, v := range list {
		if v > max {
			max = v
		}
		if v < min {
			min = v
		}
	}
	return max, min
}

// MadixSort 基数排序
// 将整数按位数切割成不同的数字，然后按每个位数分别比较
// 从高位开始，或者 从低位开始
func MadixSort(list []int) {

}

// 桶排序，以后在看吧
